/*
 * Copyright (c) 2004-2006 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Gou Pengfei
 *
 * Date:    May 2011
 */

#include <sys/time.h>
#include <cmath>

#include "base/intmath.hh"
#include "base/bitfield.hh"
#include "cpu/edge/pred/tage_type.hh"
#include "cpu/base.hh"

template<class Impl>
TAGETypeP<Impl>::TAGETypeP(DerivEdgeCPUParams *params)
    : BaseTypePredictor<Impl>(params, "TAGE"),
      _name(params->name + ".TAGETypePredictor"),
      localHistoryTableSize(params->localHistoryTableSize),
      localHistoryBits(params->localHistoryBits),
      fixedTableSize(params->btypeTageTaggedTableSize),
      defaultTableSize(params->btypeTageDefaultTableSize),
      taggedCtrBits(params->btypeTageTaggedCtrBits),
      defaultCtrBits(params->btypeTageDefaultCtrBits),
      taggedUsefulCtrBits(params->btypeTageTaggedUsefulCtrBits),
      tagBits(params->btypeTageTagBits),
      numTaggedTables(params->btypeTageNumTaggedTables),
      alpha(params->btypeTageAlpha),
      l1(params->btypeTagel1),
      blockShiftAmt(params->blockShiftAmt)
{
    if (params->btypeTageTableSizeMode == "Equal") {
        taggedTableSizeMode = Equal;
    } else if (params->btypeTageTableSizeMode == "HistPower") {
        taggedTableSizeMode = HistPower;
    } else {
        fatal("Invalid table size mode selected for tage type"
                " predictor\n");
    }

    initVars();

    if (params->btypeTageGlobalIndexMode == "AddressAndPath") {
        globalIndexMode = AddressAndPath;
    } else if (params->btypeTageGlobalIndexMode == "AddressAndCPath") {
        globalIndexMode = AddressAndCPath;
    } else if (params->btypeTageGlobalIndexMode == "AddressAndHist") {
        globalIndexMode = AddressAndHist;
    } else {
        fatal("Invalid global index mode selected for tage type"
                " predictor\n");
    }

    if (params->btypeTagePredictionMode == "GlobalOnly") {
        predictionMode = GlobalOnly;
    } else if (params->btypeTagePredictionMode == "IncludeLocal") {
        predictionMode = IncludeLocal;
    } else {
        fatal("Invalid prediction mode selected for tage type"
                " predictor\n");
    }
}

template<class Impl>
TAGETypeP<Impl>::~TAGETypeP()
{
    DPRINTF(EdgePredUnit,"TAGE destructed!\n");
}

template<class Impl>
void
TAGETypeP<Impl>::initVars()
{
    if (numTaggedTables > 4) {
        fatal("Only 4 tagged tables at most are allowed!\n");
    }

    /** Setup the history table for the local table */
    localHistoryTable.resize(localHistoryTableSize);

    localHistoryTableMask = floorPow2(localHistoryTableSize) - 1;

    for (int i = 0; i < localHistoryTableSize; ++i)
        localHistoryTable[i] = 0;

    /** Setup the history table for the local futrue file */
    localFutureFile.resize(Impl::MaxInFlightBlockNum);

    for (int i = 0; i < Impl::MaxInFlightBlockNum; ++i) {
        localFutureFile[i].index = 0;
	localFutureFile[i].history = 0;
    }
    /** Setup the local history mask */
    localHistoryMask = (ULL(0x1) << localHistoryBits) - 1;

    if (!isPowerOf2(defaultTableSize)) {
        fatal("Invalid default table size!\n");
    }

    // Set up the default table.
    defaultTable.resize(defaultTableSize);

    defaultTableMask = floorPow2(defaultTableSize) - 1;

    defaultThreshold = (ULL(0x1) << (defaultCtrBits - 1)) - 1;
    defaultThreshold = defaultThreshold / 2;

    for (int i = 0; i < defaultTableSize; ++i) {
        defaultTable[i].counter.setBits(defaultCtrBits);
        // Set to weak correct
        defaultTable[i].counter.set(defaultThreshold + 1);
        defaultTable[i].typeID = TheISA::branch;
    }

    DPRINTF(EdgePredUnit, "TAGE: set default table size to %i,"
            " mask to %#x, counter bits to %i, threshold to %i\n",
            defaultTableSize, defaultTableMask, defaultCtrBits,
            defaultThreshold);

    if (!isPowerOf2(fixedTableSize)) {
        fatal("Invalid tagged table size!\n");
    }

    // Set up the tagged tables.
    taggedTables.resize(numTaggedTables);
    taggedTableSize.resize(numTaggedTables);
    taggedTableMask.resize(numTaggedTables);
    globalHistoryMasks.resize(numTaggedTables);
    globalHistoryBits.resize(numTaggedTables);

    taggedThreshold = (ULL(0x1) << (taggedCtrBits - 1)) - 1;
    taggedThreshold = taggedThreshold / 2;
    tagMask = (ULL(0x1) << tagBits) - 1;

    for (int i = 0; i < numTaggedTables; ++i) {

        globalHistoryBits[i] =
            static_cast<uint64_t>((double)l1 * pow((double)alpha, (double)i));

        globalHistoryMasks[i] = (ULL(0x1) << globalHistoryBits[i]) - 1;

        DPRINTF(EdgePredUnit, "TAGE: set T%i history bits to %i,"
                " mask to %#x\n",
                i + 1, globalHistoryBits[i], globalHistoryMasks[i]);

        if (taggedTableSizeMode == Equal) {
            taggedTableSize[i] = fixedTableSize;
        } else if (taggedTableSizeMode == HistPower) {
            taggedTableSize[i] = ULL(0x1) << globalHistoryBits[i];
        }

        taggedTableMask[i] = floorPow2(taggedTableSize[i]) - 1;

        taggedTables[i] = new TaggedTable;
        taggedTables[i]->resize(taggedTableSize[i]);

        TaggedTable * table = taggedTables[i];

        for (int j = 0; j < taggedTableSize[i]; ++j) {
            (*table)[j].counter.setBits(taggedCtrBits);
            // Set to weak correct
            (*table)[j].counter.set(taggedThreshold + 1);
            (*table)[j].useful.setBits(taggedUsefulCtrBits);
//            (*table)[j].typeID = TheISA::seq;
        }

        DPRINTF(EdgePredUnit, "TAGE: set T%i size to %i,"
                " mask to %#x, counter bits to %i, threshold to %i,"
                " useful counter bits to %i, tag mask to %#x\n",
                i + 1, taggedTableSize[i], taggedTableMask[i],
                taggedCtrBits, taggedThreshold,
                taggedUsefulCtrBits, tagMask);
    }

    for (int i = 0; i < Impl::MaxThreads ;++i ) {
	globalHistory[i] = 0;
//        pathHistoryTable[i].resize(globalHistoryBits[numTaggedTables - 1],
//                static_cast<Addr>(0));
        pathHistoryTable[i].resize(16, static_cast<Addr>(0));
    }

    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i) {
//        checkpointEntries[i].pathHistory.resize(
//                globalHistoryBits[numTaggedTables - 1],
//                static_cast<Addr>(0));
        checkpointEntries[i].pathHistory.resize(16, static_cast<Addr>(0));
    }

    typeIdBits = floorLog2(TheISA::NumBranchType);

//    typeIdMask = static_cast<uint64_t>(typeIdBits) - 1;
    typeIdMask = (ULL(0x1) << typeIdBits) - 1;

    DPRINTF(EdgePredUnit, "TAGE: type id bits: %i"
            " type id mask: %#x\n",
            typeIdBits, typeIdMask);

    // Feed the random generator.
    srand(time(NULL));
}

template<class Impl>
void
TAGETypeP<Impl>::regStats()
{
    correctProvider
        .init(0, 5/* Allow 5 tables at most*/, 1)
        .name(name() + ".correctProvider")
        .desc("ID of correct provider.");

    incorrectProvider
        .init(0, 5/** Allow 5 tables at most*/, 1)
        .name(name() + ".incorrectProvider")
        .desc("ID of incorrect provider.");
}

template<class Impl>
void
TAGETypeP<Impl>::reset()
{
    for (int i = 0; i < defaultTableSize; ++i) {
        defaultTable[i].counter.reset();
        defaultTable[i].typeID = TheISA::seq;
    }

    for (int i = 0; i < numTaggedTables; ++i) {
        TaggedTable * table = taggedTables[i];

        for (int j = 0; j < taggedTableSize[i]; ++j) {
            (*table)[j].counter.reset();
            (*table)[j].useful.reset();
            (*table)[j].typeID = TheISA::seq;
        }
    }
	
    for (int i = 0; i < Impl::MaxThreads ;++i) {
	globalHistory[i] = 0;

        for (int j = 0; j < pathHistoryTable[i].size(); ++j) {
            pathHistoryTable[i][j] = 0;
        }
    }
	
    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i) {
        checkpointEntries[i].reset();
    }
}

template<class Impl>
inline
uint64_t
TAGETypeP<Impl>::calcLocHistIdx(Addr &block_addr, int addr_space_ID)
{
    // Get low order bits after removing instruction offset.
    assert(addr_space_ID >= 0 && addr_space_ID <= 15);

    int reverse_as_id = ((addr_space_ID & 0x1) << 3)
                        | ((addr_space_ID & 0x2) << 1)
                        | ((addr_space_ID & 0x4) >> 1)
                        | ((addr_space_ID & 0x8) >> 3);

    return ((block_addr >> blockShiftAmt) ^
           (reverse_as_id << (localHistoryBits - 4))) 
           & localHistoryTableMask;
}

template<class Impl>
inline
uint64_t
TAGETypeP<Impl>::calcLocPredIdx(Addr &block_addr, uint64_t history)
{
    uint64_t index = ((history & localHistoryMask) ^
            (block_addr >> blockShiftAmt))
            & taggedTableMask[numTaggedTables - 1];

    return index;
}

template<class Impl>
inline
uint64_t
TAGETypeP<Impl>::calcGloPredIdx(Addr &block_addr, uint64_t history,
        uint64_t path_hist, int idx)
{
    uint64_t index = ULL(-1);

    assert(idx > 0 && idx <= numTaggedTables);
    
    if (globalIndexMode == Address) {

        index = (block_addr >> blockShiftAmt) & taggedTableMask[idx - 1];

    } else if (globalIndexMode == AddressAndPath) {

        index = ((block_addr >> blockShiftAmt) ^
                (path_hist & globalHistoryMasks[idx - 1])) &
            taggedTableMask[idx - 1];

    } else if (globalIndexMode == AddressAndCPath) {

        uint64_t pattern = bits(path_hist,
                                (globalHistoryBits[idx - 1] / 2) - 1,
                                0);

        index = (((block_addr >> blockShiftAmt) <<
                    (globalHistoryBits[idx - 1] / 2)) |
                    pattern) & taggedTableMask[idx - 1];

    } else if (globalIndexMode == AddressAndHist) {

        index = ((history & globalHistoryMasks[idx - 1]) ^
                (block_addr >> blockShiftAmt))
                & taggedTableMask[idx - 1];

    } else {
        panic("Invalid global index mode selected for tage type"
                " predictor\n");
    }

    return index;
}

template<class Impl>
TheISA::BTypeID
TAGETypeP<Impl>::lookup(BlockID block_id, BlockID oldest_block_id, 
        Addr &block_addr, int addr_space_ID, ThreadID tid)
{
    uint64_t local_history_idx = 0;
    uint64_t local_history = 0;
    uint64_t local_predictor_idx = 0;
    LFFEntry lff_entry_new;

    bool provider_found = false;
    BTypeID provider_pred = TheISA::InvalidExitType;
    int provider_id = -1;
    bool alter_found = false;
    BTypeID alter_pred = TheISA::InvalidExitType;
    int alter_id = -1;

    Addr block_tag = (block_addr >> blockShiftAmt) & tagMask;

    uint64_t global_history = globalHistory[tid];
    uint64_t path_history = getPathHistory(tid);

    int idx = numTaggedTables;

    for (; idx > 0; --idx) {

        DPRINTF(EdgePredUnit, "Looking T%i table.\n", idx);

        // Last table is indexed by local history if we have local
        // information.
        if (predictionMode == IncludeLocal && idx == numTaggedTables) {

            local_history_idx = calcLocHistIdx(block_addr, addr_space_ID);

            local_history = localHistoryTable[local_history_idx];

            if (block_id != oldest_block_id && oldest_block_id != 0) {
                BlockID tmp_bid = block_id; // latest block

                do {
                    LFFEntry lff_entry;
                    tmp_bid = (tmp_bid - 1) & (Impl::MaxInFlightBlockNum - 1);
                    lff_entry = localFutureFile[tmp_bid];

                    if (lff_entry.index == local_history_idx) {
                        local_history = lff_entry.history;
                        break;
                    }
                } while (tmp_bid !=
                        (oldest_block_id & (Impl::MaxInFlightBlockNum - 1)));
            }

            //Lookup local prediction
            local_predictor_idx = calcLocPredIdx(block_addr, local_history);

            TaggedTable * table = taggedTables[idx - 1];

            Addr tag = (*table)[local_predictor_idx].tag;

            if (tag == block_tag) {
                if (!provider_found) {
                    provider_pred = (*table)[local_predictor_idx].typeID;

                    provider_found = true;
                    provider_id = idx;
                } else {
                    // If we reach here, it's panic;
                    assert(0 && "Local table should be the last table\n");
                }
            }

            continue;
        }

        uint64_t global_predictor_idx = calcGloPredIdx(block_addr,
                global_history, path_history, idx);

        TaggedTable * table = taggedTables[idx - 1];
        Addr tag = (*table)[global_predictor_idx].tag;
        
        if (tag == block_tag) {
            if (!provider_found) {
                provider_pred = (*table)[global_predictor_idx].typeID;

                provider_found = true;
                provider_id = idx;
            } else {
                assert(!alter_found);
                alter_pred = (*table)[global_predictor_idx].typeID;

                alter_found = true;
                alter_id = idx;

                // Once we found the alter, we quit.
                break;
            }
        }
    }

    if (idx == 0) {

        uint64_t default_table_idx = (block_addr >> blockShiftAmt) & 
            defaultTableMask;

        if (!provider_found) {
            DPRINTF(EdgePredUnit, "Prediction is not provided by"
                    " tagged tables\n");

            provider_pred = alter_pred =
                defaultTable[default_table_idx].typeID;

            provider_id = alter_id = idx;

        } else if (!alter_found) {
            DPRINTF(EdgePredUnit, "Alter prediction is not provided by"
                    " tagged tables\n");

            alter_pred = defaultTable[default_table_idx].typeID;
            alter_id = idx;
        }
    }

    DPRINTF(EdgePredUnit,"TAGE lookup: provider id %i, provider_pred %i,"
            " alter id %i, alter pred %i\n",
            provider_id, provider_pred,
            alter_id, alter_pred);

    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1); 

    DPRINTF(EdgePredUnit, "Checkpoint current state to frame[%i]\n", index);

    // Checkpoints the current state.
    checkpointEntries[index].blockID = block_id;
    checkpointEntries[index].globalHistory = globalHistory[tid];
    checkpointEntries[index].pathHistory = pathHistoryTable[tid];
    checkpointEntries[index].providerID = provider_id;
    checkpointEntries[index].alterID = alter_id;
    checkpointEntries[index].providerPrediction = provider_pred;
    checkpointEntries[index].alterPrediction = alter_pred;

    // Speculatively update the global history
    globalHistory[tid] = ((global_history << typeIdBits) |
            (provider_pred & typeIdMask));

    updatePathHistory(pathHistoryTable[tid], block_addr);

    if (predictionMode == IncludeLocal) {
        // Speculatively update the local history to local future
        // file, so that local histories are more precisely generated.
        lff_entry_new.index = local_history_idx;
        lff_entry_new.history = ((local_history << typeIdBits) |
                (provider_pred & typeIdMask)) &
                localHistoryMask;
        localFutureFile[index] = lff_entry_new;
    }

    return provider_pred;
}

template<class Impl>
TheISA::BTypeID
TAGETypeP<Impl>::update(BlockID block_id, Addr &block_addr, 
        int addr_space_id, BTypeID actual_type_id, ThreadID tid)
{
    uint64_t local_history_idx = 0;
    uint64_t local_predictor_hist = 0;
    uint64_t local_predictor_hist_new = 0;

    assert(actual_type_id >= 0 && actual_type_id < TheISA::NumBranchType);

    // Read L1 tables of exit predictor
    uint64_t index = block_id & (Impl::MaxInFlightBlockNum -1);

    DPRINTF(EdgePredUnit, "Update from frame[%i]\n", index);

    assert(checkpointEntries[index].blockID == block_id);

    int provider_id = checkpointEntries[index].providerID;

    assert(provider_id >= 0 && provider_id <= numTaggedTables);

    uint64_t global_predictor_hist = checkpointEntries[index].globalHistory;

    uint64_t path_hist = getPathHistory(block_id, tid);

    uint64_t provider_table_idx = 0;

    // Calculate table index
    if (predictionMode == IncludeLocal && provider_id == numTaggedTables) {
        local_history_idx = calcLocHistIdx(block_addr, addr_space_id);
        local_predictor_hist = localHistoryTable[local_history_idx];

        //Update local history tables
        local_predictor_hist_new = ((local_predictor_hist << typeIdBits) |
                                   (actual_type_id & typeIdMask)) &
                                   localHistoryMask;

        localHistoryTable[local_history_idx] = local_predictor_hist_new;
        
        provider_table_idx = calcLocPredIdx(block_addr, local_predictor_hist);

    } else if (provider_id > 0) {
           
        provider_table_idx = calcGloPredIdx(block_addr,
                                            global_predictor_hist,
                                            path_hist,
                                            provider_id);

    } else {
        // Provider is the default table
        provider_table_idx = (block_addr >> blockShiftAmt) & defaultTableMask;
    }

    BTypeID current_type_id = TheISA::InvalidExitType;

    // Update the counters
    if (provider_id == 0) {
        assert(provider_table_idx < defaultTableSize);

        DefaultTableEntry & entry = defaultTable[provider_table_idx];

        current_type_id = entry.typeID;

        // Update the content if we're under the threshold.
        if (entry.counter.read() <= defaultThreshold) {
            entry.typeID = actual_type_id;
        }

        if (actual_type_id == current_type_id) {
            entry.counter.increment();

            correctProvider.sample(provider_id);
        } else {
            entry.counter.decrement();

            incorrectProvider.sample(provider_id);
        }

    } else {
        assert(provider_table_idx < taggedTableSize[provider_id - 1]);

        TaggedTableEntry & entry =
            (*(taggedTables[provider_id - 1]))[provider_table_idx];

        current_type_id = entry.typeID;

        if (entry.counter.read() <= taggedThreshold) {
            entry.typeID = actual_type_id;
        }

        BTypeID alter_pred = checkpointEntries[index].alterPrediction;

        if (actual_type_id == current_type_id) {
            entry.counter.increment();

            correctProvider.sample(provider_id);

            // Update the useful counters
            if (alter_pred != actual_type_id) {
                entry.useful.increment();

                DPRINTF(EdgePredUnit, "Increment the useful counter for "
                        "T%i to %i\n", provider_id, entry.useful.read());
            }
        } else {
            entry.counter.decrement();

            incorrectProvider.sample(provider_id);

            // Update the useful counters
            if (alter_pred != actual_type_id) {
                entry.useful.decrement();
                
                DPRINTF(EdgePredUnit, "Decrement the useful counter for "
                        "T%i to %i\n", provider_id, entry.useful.read());
            }
        }
    }

    // Try to allocate a new entry for this prediction.
    //
    // If a misprediction happened in the local table, we try to
    // allocate an entry in global tables. So reset the provider id to
    // 0.
    if ((predictionMode == IncludeLocal) && 
            (provider_id == numTaggedTables) &&
            (actual_type_id != current_type_id)) {

        provider_id = 0;

        // Clear the entry if the useful counter is zero
        uint64_t table_idx = calcLocPredIdx(block_addr, local_predictor_hist);

        TaggedTable * table = taggedTables[numTaggedTables - 1];
        TaggedTableEntry & entry = (*table)[table_idx];

        if (entry.useful.read() == 0) {
            entry.tag = ULL(-1);
            entry.typeID = TheISA::branch;
            entry.counter.set(taggedThreshold + 1);
        }
    }

    if ((provider_id < numTaggedTables) &&
            (actual_type_id != current_type_id)) {

        int rand_num = rand() % 100;
        int start_idx = provider_id + 1;

        // Number of potential candidates except provider + 1.
        int candidate_num = numTaggedTables - provider_id - 1;

        for (int i = 0; i < candidate_num; ++i) {

            int lower = 50 + (i * (50 / candidate_num));
            int upper = 50 + (i + 1) * (50 / candidate_num);

            if (rand_num >= lower && rand_num < upper) {
                start_idx = provider_id + i + 2;
                break;
            }
        }

        DPRINTF(EdgePredUnit, "Random number: %i. Begin searching at %i\n",
                rand_num, start_idx);

        bool allocated = false;
        for (int idx = start_idx; idx <= numTaggedTables; ++idx) {

            uint64_t table_idx;

            table_idx = calcGloPredIdx(block_addr,
                                       global_predictor_hist,
                                       path_hist,
                                       idx);

            if (predictionMode == IncludeLocal && idx == numTaggedTables) {
                table_idx = calcLocPredIdx(block_addr, local_predictor_hist);
            }

            TaggedTable * table = taggedTables[idx - 1];
            TaggedTableEntry & entry = (*table)[table_idx];

            if (entry.useful.read() == 0) {

                entry.tag = (block_addr >> blockShiftAmt) & tagMask;
                // Set to strong not useful
                entry.useful.reset();
                // Set to weak correct
                entry.counter.set(taggedThreshold + 1);

                entry.typeID = actual_type_id;

                allocated = true;

                DPRINTF(EdgePredUnit, "Allocate entry in T%i for"
                        " Bid:%lli @%#x\n", idx, block_id, block_addr);

                break;
            }
        }

        // If no entry is allocated, we decrease useful counters of
        // candidate entries.
        if (!allocated) {
            for (int idx = provider_id + 1; idx <= numTaggedTables; ++idx) {

                uint64_t table_idx;

                table_idx = calcGloPredIdx(block_addr,
                                           global_predictor_hist,
                                           path_hist,
                                           idx);

                if (predictionMode == IncludeLocal && idx == numTaggedTables) {
                    table_idx = calcLocPredIdx(block_addr, local_predictor_hist);
                }

                TaggedTable * table = taggedTables[idx - 1];
                TaggedTableEntry & entry = (*table)[table_idx];
                entry.useful.decrement();
            }
        }
    }

    return current_type_id;
}

template<class Impl>
void
TAGETypeP<Impl>::squash(BlockID block_id, Addr block_pc, 
        BTypeID type_id, ThreadID tid)
{
    uint64_t global_history = 0;

    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1) ;

    DPRINTF(EdgePredUnit, "Squash from frame[%i] due to misprediction\n",
            index);

    assert(checkpointEntries[index].blockID == block_id);

    if (predictionMode == IncludeLocal) {
        // Squash the local future file.
        LFFEntry oldLFFEntry, newLFFEntry;
        oldLFFEntry = localFutureFile[index];
        newLFFEntry.index = oldLFFEntry.index;
        newLFFEntry.history = ((oldLFFEntry.history & (~typeIdMask)) |
                (type_id & typeIdMask))
                & localHistoryMask;
        localFutureFile[index] = newLFFEntry;
    }

    // Restore global history to state prior to this block.
    global_history = checkpointEntries[index].globalHistory;

    globalHistory[tid] = ((global_history << typeIdBits) |
                         (type_id & typeIdMask));

    PathHistory path = checkpointEntries[index].pathHistory;
    updatePathHistory(path, block_pc);
    pathHistoryTable[tid] = path;

    DPRINTF(EdgePredUnit, "TAGE: Squashing BP to Block [bid:%i].\n", 
            block_id);
}

template<class Impl>
void
TAGETypeP<Impl>::squash(BlockID block_id, ThreadID tid)
{
    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1);

    DPRINTF(EdgePredUnit, "Squash from frame[%i] due to fault\n",
            index);

    assert(checkpointEntries[index].blockID == block_id);

    globalHistory[tid] = checkpointEntries[index].globalHistory;
    pathHistoryTable[tid] = checkpointEntries[index].pathHistory;
}

template<class Impl>
void 
TAGETypeP<Impl>::updatePathHistory(PathHistory &path_history, Addr new_pc)
{
    DPRINTF(EdgePredUnit, "Update path history,"
            " Pop: %#x; Push: %#x\n",
            path_history.back(),
            new_pc);

    path_history.pop_back();

    new_pc >>= blockShiftAmt;

    path_history.push_front(new_pc);
}

template<class Impl>
uint64_t
TAGETypeP<Impl>::getPathHistory(BlockID block_id, ThreadID tid)
{
    int index = block_id & (Impl::MaxInFlightBlockNum - 1);

    assert(checkpointEntries[index].blockID == block_id);

    PathHistory path = checkpointEntries[index].pathHistory;

    uint64_t path_hist = 0;

    for (int i = 0; i < path.size(); i++) {
        if (i < 16) {
            // Take 4 bits from each path address
            path_hist |= ((path[i] & ULL(0xF)) << (i * 4));
        }
    }

    return path_hist;
}

template<class Impl>
uint64_t
TAGETypeP<Impl>::getPathHistory(ThreadID tid)
{
    PathHistory path = pathHistoryTable[tid];

    uint64_t path_hist = 0;

    for (int i = 0; i < path.size(); i++) {
        if (i < 16) {
            // Take 4 bits from each path address
            path_hist |= ((path[i] & ULL(0xF)) << (i * 4));
        }
    }

    return path_hist;
}

template<class Impl>
uint64_t
TAGETypeP<Impl>::getGlobalHistory(BlockID block_id, ThreadID tid)
{
    int index = block_id & (Impl::MaxInFlightBlockNum - 1);

    assert(checkpointEntries[index].blockID == block_id);

    uint64_t hist = checkpointEntries[index].globalHistory;

    return hist;
}

